package com.leetcode.LeetCode精选TOP面试题;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 覃国强
 * @date 2022-07-17 13:32
 */
public class 题库_0239_滑动窗口最大值 {

  static
  class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
      int[] answer = new int[nums.length - k + 1];
      Deque<Integer> queue = new ArrayDeque<>();
      for (int i = 0; i < k; ++i) {
        addNum2Queue(queue, nums, i, k);
      }
      int index = 0;
      answer[index++] = nums[queue.getFirst()];

      for (int i = k; i < nums.length; ++i) {
        addNum2Queue(queue, nums, i, k);
        answer[index++] = nums[queue.getFirst()];
      }

      return answer;
    }

    private void addNum2Queue(Deque<Integer> queue, int[] nums, int i, int k) {
      while (!queue.isEmpty() && i - queue.getFirst() >= k) {
        queue.removeFirst();
      }

      while (!queue.isEmpty() && nums[queue.getLast()] <= nums[i]) {
        queue.removeLast();
      }
      queue.addLast(i);
    }
  }

}
